package com.shawn.algorithm.dynamicprogramming;

import java.util.Arrays;

/**
 * 最小路径和
 */
public class MinimumPathSum {

	public int minPathSum(int[][] grid) {
		if (grid.length == 0) {
			return 0;
		}

		int r = grid.length;
		int c = grid[0].length;

		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				int leftSum = (j > 0) ? grid[i][j - 1] : Integer.MAX_VALUE;
				int topSum = (i > 0) ? grid[i - 1][j] : Integer.MAX_VALUE;
				if (i == 0 && j == 0) {
					continue;
				}

				grid[i][j] += Math.min(leftSum, topSum);
			}
		}
		return grid[r - 1][c - 1];
	}

	public int minPathSum2(int[][] grid) {
		int[][] minPath = new int[grid.length][grid[0].length];
		minPath[0][0] = grid[0][0];
		// column
		for (int i = 1; i < grid[0].length; i++) {
			minPath[0][i] = minPath[0][i - 1] + grid[0][i];
		}

		// row
		for (int j = 1; j < grid.length; j++) {
			minPath[j][0] = minPath[j - 1][0] + grid[j][0];
		}

		for (int i = 1; i < grid.length; i++) {
			for (int j = 1; j < grid[0].length; j++) {
				if (minPath[i - 1][j] < minPath[i][j - 1]) {
					minPath[i][j] = minPath[i - 1][j] + grid[i][j];
				} else {
					minPath[i][j] = minPath[i][j - 1] + grid[i][j];
				}
			}
		}

		return minPath[grid.length - 1][grid[0].length - 1];
	}

	public static void main(String[] args) {
		MinimumPathSum min = new MinimumPathSum();
		int[][] grid = {
			{1, 3, 1}, {1, 5, 1}
		};
		System.out.println(Arrays.deepToString(grid));
		System.out.println(min.minPathSum2(grid));
	}
}
